/*
 * @Descripttion: 
 * @version: 
 * @Author: lily
 * @Date: 2021-05-26 15:01:37
 * @LastEditors: lily
 * @LastEditTime: 2021-05-26 15:35:03
 */
/*
 * @lc app=leetcode.cn id=238 lang=javascript
 *
 * [238] 除自身以外数组的乘积
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number[]}
 */

//  思想：
//  res[i] = mul(0,i-1) * mul(i+1,len-1)
//  为了只使用O(1)空间复杂度，利用输出数组存储左右乘积

//  复杂度：O(n)  O(1)

var productExceptSelf = function (nums) {
    const len = nums.length
    let res = new Array(len)
    res[0] = 1
    // 计算当前元素左边的乘积
    for (let i = 1; i < len; i++) {
        res[i] = res[i - 1] * nums[i - 1]
    }
    // 再乘以当前元素右边的乘积
    let k = 1
    for (let i = len - 1; i >= 0; i--) {
        res[i] *= k
        k *= nums[i]
    }
    return res
};
// @lc code=end


console.log(productExceptSelf([1, 2, 3, 4]));
